//
// Created by zhou on 2021/11/7.
//
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    pair<int,int> convert(const string s,int x,int y){
        while(x>=0&&y<s.length()&&s[x]==s[y]){
            x--;
            y++;
        }
        return {x+1,y-1};
    }
    string longestPalindrome1(string s) {
        int start=0,end=0;
        for(int i=0;i<s.length();i++){
            auto [left1,right1]=convert(s,i,i);
            auto [left2,right2]=convert(s,i,i+1);
            if(right1-left1+1>end-start+1){
                start=left1;
                end=right1;
            }
            if(right2-left2>end-start+1){
                start=left2;
                end=right2;
            }
        }
        return s.substr(start,end-start+1);
    }
    string longestPalindrome(string s) {
        int len=s.length();
        vector<vector<int>> dp(len,vector<int>(len));
        int left=0;
        int longest=1;
        for(int i=0;i<len;i++){
            dp[i][i]=1;
            if(i<len-1){
                if(s[i]==s[i+1]) {
                    dp[i][i + 1] = 1;
                    longest = 2;
                    left = i;
                }
            }
        }
        for(int l=2;l<len;l++){
            for(int i=0;i+l<len;i++){
                int j=l+i;
                if(s[i]==s[j]&&dp[i+1][j-1]==1){
                    dp[i][j]=1;

                    left=i;
                    longest=j-i+1;}


            }
        }
        return s.substr(left,longest);
    }
};
int main(){
    string s="abacav";
    Solution solution;
    cout<<solution.longestPalindrome1(s);
}
